package com.github.wings27.interview.DataStructure;

/**
 * Created with IntelliJ IDEA.
 * Project Name: common-interview-problems
 * Date Created: 2013/10/28 下午7:41
 *
 * @author wings
 */
public class CycleLinkList {
    private static LinkListNode head;

    public static void init() {
        //init
        head = new LinkListNode(0);
        head.next = new LinkListNode(1);
        head.next.next = new LinkListNode(2);
        head.next.next.next = new LinkListNode(3);
        head.next.next.next.next = new LinkListNode(4);
        head.next.next.next.next.next = new LinkListNode(5);
        head.next.next.next.next.next.next = new LinkListNode(6);
        head.next.next.next.next.next.next.next = head;
    }

    public static void main(String[] args) {
        init();
    }

    /**
     * 环状单链表，给定指向某个节点的指针，编写算法求离其最远的节点  --人人网笔试题
     */
    public static LinkListNode findFarthestNode(LinkListNode node) {
        if (node == null || node.next == null) {
            return node;
        }
        int counter = 0;
        LinkListNode curNode = node;
        while (curNode.next != node) {
            counter++;
            curNode = curNode.next;
        }
        int mid = (counter + 1) / 2;
        while (mid-- > 0) {
            node = node.next;
        }
        return node;
    }

    /**
     * 一些人围成一圈，从第k个人开始报数，数到m的人出列，下一个人继续报数，求最后出列的人  --约瑟夫环问题
     */
    public static LinkListNode josephus(LinkListNode linkListHead, int k, int m) {
        LinkListNode node = linkListHead;
        while (k-- > 0) {
            node = node.next;
        }
        LinkListNode pre = node;
        while (node != node.next) {
            int count = m;
            while (count-- > 0) {
                pre = node;
                node = node.next;
            }
            System.out.println(node.data);
            pre.next = node.next;
            node = node.next;
        }
        System.out.println(node.data + "(Last one)");
        return node;
    }

    /**
     * Created with IntelliJ IDEA.
     * Project Name: common-interview-problems
     * Date Created: 2013/10/28 下午7:39
     *
     * @author wings
     */
    public static class LinkListNode {
        public int data;
        public LinkListNode next;

        public LinkListNode(int value) {
            this.data = value;
        }
    }
}
